﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once

// 64位下页号不够用，开辟更大的页号类型
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif 


#ifdef _WIN32
	#include <Windows.h>
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <thread>
#include <mutex>
#include <unordered_map>
using std::cout;
using std::endl;


static const size_t MAXBYTES = 256 * 1024;  // 线程最多申请的内存大小
static const size_t LISTNUMS = 208;         // 
static const size_t NPAGES = 129;           // PageCache中限制的最大页数
static const size_t PAGE_SHIFT = 13;        // 一页的内存大小 2^13
static const size_t LIMIT_PAGES = 32;       // 256KB --> 32页


static inline void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux系统下使用brk，mmp来申请
#endif

	if (ptr == nullptr) throw std::bad_alloc();

	return ptr;
}

static inline void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else	
	// Linux下的接口待开发
#endif // _WIN32

}

static void*& NextObj(void* src)
{
	return *(void**)src;
}

// 管理返回的自由链表
// 只提供管理，具体的内存块多大？不关心，根据后面的哈希桶映射进行表示.
class FreeList
{
public:
	void push(void* obj)
 	{
		//插入一个内存块
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void* pop()
	{
		assert(_freeList);
		void* obj = _freeList;
		_freeList = NextObj(_freeList);
		--_size;
		return obj;
	}

	void append(void* start, void* end, size_t size)
	{
		assert(end);
		NextObj(end) = _freeList;
		_freeList = start;
		_size += size;

		//int cnt = 0;
		//void* cur = start;
		//while (cur != NextObj(end))
		//{
		//	cur = NextObj(cur);
		//	++cnt;
		//}

		//if (cnt != size)
		//{
		//	int x = 0;
		//}
	}

	void popRange(void*& start, size_t size)
	{
		assert(size <= _size);
		if (_size < size)
		{
			return;
		}

		start = _freeList;
		void* end = _freeList;

		

		while (size > 1 && NextObj(end) != nullptr)
		{
			end = NextObj(end);
		}

		_freeList = NextObj(end);
		NextObj(end) = nullptr;

		_size -= size;

	}

	bool empty() const
	{
		return _freeList == nullptr;
	}

	size_t& getMaxSize()
	{
		return _maxsize;
	}

	size_t size() const 
	{
		return _size;
	}


	void* begin() const
	{
		return _freeList;
	}

private:
	void* _freeList = nullptr; // 自由链表的首个元素，简单的单链表
	size_t _maxsize = 1;       // 初始值设置为1
	size_t _size = 0;          // 当前挂载的小块内存的个数
};


class sizeClass
{
private:
	static inline size_t _index(size_t bytes, size_t align_shift)
	{
		//计算是哪一个链表
		//这里的bytes要减去前面的桶的bytes:
		//注意这里的align_shift并不是对齐数，而是log对齐数
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	//
	
public:
	static inline size_t _roundUp(size_t size, size_t alignNum)
	{
		// 计算要分配多少内存
		// 不是要多少就精准的给多少，由于采用的是桶锁，所以要计算一下到底需要分配多少内存
		// 比如说用户申请5byte，那么就只能给8byte
		// 丑陋版实现
		//return ((size % alignNum) + 1) * alignNum;
		// 位运算效率更高
		return (size + alignNum - 1) & ~(alignNum - 1);
	}
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128] 8byte对齐      					freelist[0,16)
	// [128+1,1024] 16byte对齐  					freelist[16,72)
	// [1024+1,8*1024] 128byte对齐  			freelist[72,128)
	// [8*1024+1,64*1024] 1024byte对齐    		freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对齐  	freelist[184,208)
	// 
	// -------------------------------------------------------------
	// 某一个对齐数代表是哪一段的链表，而index代表具体的是哪一个链表
	// 计算是哪一个桶



	static inline size_t index(size_t bytes)
	{
		assert(bytes < MAXBYTES);
		//一个数组
		size_t group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128)
		{
			return _index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _index(bytes - 1024, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _index(bytes = 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			//到这里的内存一定是小于等于256 * 1024的，因为前面已经判断过了
			return _index(bytes - 64 * 1024, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			//给不了啊亲
			assert(false);
		}
		return -1;
	}


	//计算要分配多大的空间
	static inline size_t roundUp(size_t size)
	{
		if (size <= 128)
		{
			return _roundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _roundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _roundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _roundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _roundUp(size, 8 * 1024);
		}
		else
		{
			// 按照一页对齐
			return _roundUp(size, 1 << PAGE_SHIFT);
		}
		return -1;
	}

	//计算每次分配的内存块个数
	static size_t numMoveSize(size_t bytes)
	{
		size_t num = MAXBYTES / bytes;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	static size_t numMovePage(size_t bytes)
	{
		// 返回对应要申请的页数
		size_t num = numMoveSize(bytes);
		size_t size = bytes * num;
		size_t page_nums = size >> PAGE_SHIFT;        

		if (page_nums == 0)
		{
			return 1;
		}

		return page_nums;
	}
};


struct Span
{
	PAGE_ID _pageID = 0;       // 起始的页号
	size_t _n = 0;             // 页数

	Span* _prev = nullptr;     // prev
	Span* _next = nullptr;     // next

	size_t _usedCnt = 0;       // 使用小块内存的数量
	void* _freeList = nullptr; // 切好的内存块地址

	bool isUsed = false;       // 当前span是否能够被回收

	size_t _objSize = 0;           // 当前span管理的小块内存的大小
};


/// <summary>
/// 双向带头链表
/// </summary>
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	void insert(Span* pos, Span* newSpan)
	{
		// 头插
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;

	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		if (pos->_prev == nullptr || pos->_next == nullptr)
		{
			int x = 0;
		}

		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

	}

	bool empty()
	{
		return _head->_next == _head;
	}


	Span* Begin()
	{
		return _head->_next;
	}
	
	Span* End()
	{
		// 返回最后一个有效元素的下一个元素
		return _head;
	}

	//获取链表中一个span
	Span* popFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
		//assert(!empty());

		////Span* res = _head->_next;
		////Span* next = res->_next;
		////res->_prev = nullptr;
		////res->_next = nullptr;

		//////连接
		////_head->_next = next;
		////next->_prev = _head;

		//return res;
	}

	void pushFront(Span* span)
	{
		insert(Begin(), span);
	}
private:
	Span* _head;      // 带头双向列表，head是哨兵位
public:
	std::mutex _mtx;  // 这里是桶锁
};
